Data processing systems which use virtual addressing are well known. Many data processing systems include, for example, a processing unit (PU) and a storage unit (SU). The processing unit contains the sequencing and processing facilities for instruction execution, interruption action, timing functions, initial program loading and other machine related functions. The storage unit is addressable and provides for high-speed processing of data by the processing unit. The storage unit may be either physically integrated with the processing unit or constructed in stand-alone units.
In general, address spaces reside in the storage unit wherein an address space is a consecutive sequence of integer numbers (or virtual addresses) which together with transformation parameters allow each number to be associated with a location in the storage unit.
When a virtual address is used by a processing unit to access the storage unit, it is first converted, by means of dynamic address translation (DAT), to a real address, and then, by means of prefixing, to an absolute address.
Dynamic address translation uses various levels of tables as mapping parameters. In prior computer systems, the mapping parameters include origin and length of a table and these mapping parameters are typically found in a control register or at a location specified by an access register.
Typically, dynamic address translation uses segment-table designations in different control registers or at locations specified by access registers. The choice is determined by the translation mode. In a typical computer system operating according to published IBM Principles Of Operation, the mode of operation is specified in a current program-status word (PSW). In such systems, four translation modes are available, namely, primary-space mode, secondary-space mode, access-register mode (AR-mode), and home-space mode. Different address spaces are addressable depending on the translation mode.
Dynamic address translation typically translates a virtual address of a computer system to a real address of a storage unit by means of translation tables. The bit string comprising a virtual address is divided into one or more table indexes and may also include a byte or other lower level address. A highest-level first table index is augmented by a first table width starting at a first table origin to form a first address of a first-table entry in the first table. A second table index is augmented by a second table width starting at a second table origin, obtained from the entry of the first table, to form a second address of a second-table entry in the second table. This operation continues until the table indexes of all of the tables have been processed. The entry in the last table forms the real address, when combined with any lower order address, of a location in the storage unit.
For larger tables, a common practice is to include in a higher-level table that designates an entry in a lower-level table, a table-length field indicating the length of the designated lower-level table. Such a table-length field is typically a bit string of n bits. The higher-order n bits of an index are compared to the table-length bits for the corresponding table. If the n bits of the index are less than or equal to the value of the table-length bits, the index is considered valid and processing continues and the translation occurs. If the n bits of the index are greater than the value of the table-length bits, the index is considered invalid and processing does not continue and a processing exception occurs. The processing exception causes a processing interruption so that the translation does not proceed. The storage of a table-length field has the advantage of saving storage that would be allocated for unneeded addresses beyond the end of the table.
As address spaces have grown larger, for example, as is attendant the change from 31-bit addressing architectures to 64-bit architectures, the problem of tables using unneeded address space (sometimes called sparsely populated address space) has become even more of a problem. One proposed solution appears in U.S. Pat. No. 6,801,993. In that patent, in addition to prior checking with a high-order comparison to determine if unneeded higher-order addresses are specified beyond the end of the table, a prior lower-order comparison is also performed to determine if unneeded lower-order addresses occur lower than the table start address (table offset). If the prior low-order comparison indicates that the indexing is at an address equal to or greater than the start address (table offset) of the table, then the indexing is permitted to continue. However, if the prior low-order comparison indicates that the indexing is at an address less than the start address, the index is considered invalid and processing does not continue and a processing exception occurs.
Unfortunately, the low-order comparison prior processing of the U.S. Pat. No. 6,801,993 is always present and hence consumes execution time even when the indexing is at an address equal to or greater than the start address (table offset) of the table. There is a need for improved processing that does not require the prior low-order comparison prior to indexing.
In light of the foregoing background, there is a need for improved indexing in dynamic address translation of indexing systems particularly for sparsely populated address spaces.